package com.zhugang.week07;

/**
 * @program algorithms
 * @description: buildTree
 * @author: chanzhugang
 * @create: 2022/07/22 23:27
 */
public class ConstructFromPreIn {


    /**
     * 105 从前序和中序遍历序列构造二叉树
     *
     * @param preorder
     * @param inorder
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 难理解
        return myBulidTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    private TreeNode myBulidTree(int[] preorder, int i, int j, int[] inorder, int p, int r) {
        if (i > j) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[i]);

        int q = p;
        while (q <= r && inorder[q] != preorder[i]) {
            // 在中序里找根节点
            // 找左子树分割点
            q++;
        }
        // 左子树的大小
        int leftTreeSize = q - p;

        // 构建左子树：画两个图理解
        TreeNode leftNode = myBulidTree(preorder, i + 1, i + leftTreeSize, inorder, p, q - 1);
        // 构建右子树
        TreeNode rightNode = myBulidTree(preorder, i + leftTreeSize + 1, j, inorder, q + 1, r);
        root.left = leftNode;
        root.right = rightNode;
        return root;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}